#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution 
{
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        deque<int> dq;
        vector<int> result;
        int length = nums.size();
        if(length <= k)
        {
            auto it = max_element(nums.begin(), nums.end());
            result.push_back(*it);
            return result;
        }
        for(int i = 0; i < k; i++)
        {
            if(!dq.empty())
            {
                if(nums[dq.back()] >= nums[i])
                {
                    dq.push_back(i);
                    continue;
                }
                while (!dq.empty() && nums[dq.back()] < nums[i])
                {
                    dq.pop_back();
                }
                dq.push_back(i);
            }
            else
            {
                dq.push_back(i);
            }
        }
        result.push_back(nums[dq.front()]);

        for(int i = k; i < length; i++)
        {
            if(dq.front() < i - k + 1)
            {
                dq.pop_front();
            }
            if(!dq.empty())
            {
                if(nums[dq.back()] >= nums[i])
                {
                    dq.push_back(i);
                    result.push_back(nums[dq.front()]);
                    continue;
                }
                while (!dq.empty() && nums[dq.back()] < nums[i])
                {
                    dq.pop_back();
                }
                dq.push_back(i);
            }
            else
            {
                dq.push_back(i);
            }
            result.push_back(nums[dq.front()]);
        }
        return result;
    }
};

int main()
{
    Solution solution;

    // 测试案例1: 基本滑动窗口
    vector<int> test1 = {1, 3, -1, -3, 5, 3, 6, 7};
    int k1 = 3;
    cout << "测试案例1: nums = [1,3,-1,-3,5,3,6,7], k = 3" << endl;
    vector<int> result1 = solution.maxSlidingWindow(test1, k1);
    cout << "结果: [";
    for (int i = 0; i < result1.size(); i++) {
        cout << result1[i];
        if (i < result1.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [3,3,5,5,6,7]" << endl << endl;

    // 测试案例2: k等于数组长度
    vector<int> test2 = {1};
    int k2 = 1;
    cout << "测试案例2: nums = [1], k = 1" << endl;
    vector<int> result2 = solution.maxSlidingWindow(test2, k2);
    cout << "结果: [";
    for (int i = 0; i < result2.size(); i++) {
        cout << result2[i];
        if (i < result2.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [1]" << endl << endl;

    // 测试案例3: 全递增数组
    vector<int> test3 = {1, 2, 3, 4, 5};
    int k3 = 2;
    cout << "测试案例3: nums = [1,2,3,4,5], k = 2" << endl;
    vector<int> result3 = solution.maxSlidingWindow(test3, k3);
    cout << "结果: [";
    for (int i = 0; i < result3.size(); i++) {
        cout << result3[i];
        if (i < result3.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [2,3,4,5]" << endl << endl;

    // 测试案例4: 全递减数组
    vector<int> test4 = {5, 4, 3, 2, 1};
    int k4 = 2;
    cout << "测试案例4: nums = [5,4,3,2,1], k = 2" << endl;
    vector<int> result4 = solution.maxSlidingWindow(test4, k4);
    cout << "结果: [";
    for (int i = 0; i < result4.size(); i++) {
        cout << result4[i];
        if (i < result4.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [5,4,3,2]" << endl << endl;

    // 测试案例5: 有负数的情况
    vector<int> test5 = {-1, -2, -3, 0, 1, 2};
    int k5 = 3;
    cout << "测试案例5: nums = [-1,-2,-3,0,1,2], k = 3" << endl;
    vector<int> result5 = solution.maxSlidingWindow(test5, k5);
    cout << "结果: [";
    for (int i = 0; i < result5.size(); i++) {
        cout << result5[i];
        if (i < result5.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [0,1,2]" << endl << endl;

    return 0;
}